FIG. 1 shows a multiple-input multiple-output (MIMO) wireless transmitter/receiver 100 for n=2 streams. MIMO transmitter 102 includes two antennas which transmit original data x1 and x2, where the antennas are typically separated by a short distance, which may be a quarter of a wavelength for the carrier frequency, or any convenient separation distance. For each separate transmit symbol stream X1, X2 the value received at receiver 104 inputs Y1 and Y2 represents the superposition of these X1 and X2 symbols according to the communications channel between each transmit antenna and receive antenna. The object of receiver 104 is to recover estimates x1 and x2 of the originally transmitted data streams x1 and x2. For a 2×2 (2 input, 2 output) transmitter/receiver pair, the channels for input y1 are H11 and H12, and the channels for input y2 are H12 and H22.
FIG. 2 shows the matrix equations of operation for the receiver of FIG. 1, where H is known as the channel estimate matrix, and is populated with channel characteristic values determined during preamble time.
FIG. 3 shows a 3×3 MIMO transmitter/receiver link, where transmitter 302 includes three transmit antennas and receiver 204 includes three receive antennas. The respective communications channels for input y1, y2, and y3 are {h11, h12, h13}, {h21, h22, h23}, and {h31, h32, h33}. Each transmit symbol stream X1, X2, X3 typically carries a unique stream of data, and the objective of the MIMO receiver 304 is to segregate and recover each stream of data in the form of a hard decision representing the most likely transmitted value, and a soft decision representing the certainty of each bit of the hard decision. FIG. 4 shows the matrix equations for the transmitter and receiver of FIG. 3. As before, Y is the transmitted value, H is the channel estimate matrix, X is the received value, and N is the channel noise.
FIG. 5 shows a transformation which is useful for separating superpositioned streams of symbol data containing x1 and x2 into their separated constituent values. Equation 5.1 is the previously described receiver equation, and equation 5.2 introduces the QR transformation, where the matrix R is in the form of an upper triangular matrix. This results in the matrix form of equation 5.7, which produces equation 5.9 which is reduced to one x2 variable, and equation 5.8 which has both x1 and x2 variables. By transforming all of the possible Y values into Z values through multiplication by QH (Hermitian of the Q matrix), it is possible to directly solve equation 5.9 for the x2 value using a metric such as minimum distance from z2. This can be done in by computing a distance metric to z2, where z2 is calculated by multiplying received Y by QH, and subtracting each of the 64 possible QAM-64 x2 symbol r22*x2, for the case where the number of possible symbols k is 64. The symbol with the minimum metric is the most likely transmitted symbol. It is then possible to substitute this value x2 into equation 5.8 with z1 to solve for x1. The noise terms of equation 5.7 are ignored, as they represent non-deterministic values forming the expanded square regions 604 around possible symbol points 602 of FIG. 6, as will be described.
FIG. 6 shows the constellation diagram in I and Q space for QAM-64, whereby 64 different symbols may be transmitted using the I and Q data values by using variations in amplitude and phase to place the transmitted signal into one of the constellation points. Point 602 represents an estimated transmit value x1, and region y1 604 represents a region of points which would be resolved to the most likely estimated transmit value x1.
FIG. 7 shows the operation of a single channel maximum likelihood (ML) decision decoder operating in the QAM-64 constellation of FIG. 6. In a first step 702, a complex signal y is received. From the channel estimation value h, each of the 64 possible constellation symbols x1 through x64 is multiplied by h and the distance from the received symbol y to each of the 64 possible h*x values is computed. The hard decision of the decoder is the estimated x associated with the minimum distance metric m0, shown in step 706. In step 708, the soft decision is made, whereby for each of the 6 bits of the hard decision, the minimum metric m1 (among 64 values) for the complement of the bit of the hard decision is found. The soft decision value for each bit is then calculated from |m02−m12|*sgn(hard decision) in conjunction with a prior art technique such as the Max-Log-MAP approximation.
FIG. 8 illustrates an example of the operation of a maximum likelihood receiver according to the flowchart of FIG. 7. An incoming symbol y is received, and a distance metric 804 from the received symbol to all 64 possible symbols is computed. The minimum distance metric value shown as 3 is associated with hard decision 806, corresponding to step 706 of FIG. 7. The soft decision computation for the hard decision bit of column 810 is done by finding the minimum distance metric for the complement (1 in this example), where the hard decision bit is 0. For all decisions with the complement of the corresponding decision bit (column 1, value 1 in this example), the minimum metric m1 is 22, and the soft decision value is calculated from (|32−222|)*(−1), where sgn(1)=1, and sgn(0)=−1. The soft decision value is computed in this manner, resulting in a soft decision comprising 6 values, one value for each of the hard decision bits.
FIGS. 9A and 9B illustrate examples of relatively simple decoders for single channel applications, and FIG. 10 shows the dramatic increase in complexity when performing maximum likelihood decision decoding on multiple channels of MIMO channels. In FIG. 9A, the input symbol y 902 comprising I and Q values is accompanied by a channel estimate H 914. The channel estimate 914 is used to generate a list of 64 possible table entries 916, and the distance of the received symbol y is computed 904 for each of the 64 values. Hard decision decoder 906 selects the minimum distance from the 64 calculated distances, and the soft decision calculation 908 is done for each bit of the hard decision, as was described earlier. FIG. 9B shows a single channel ML decoder with a variable transformation 950, and LLR (Log Likelihood Ratio) 978 soft decision 982 according to the method of Tosato described in U.S. Patent Application 2004/0091058. The incoming symbol y 952 accompanied by channel estimate 954 is applied to a QR decomposition function 956, which produces an R value or matrix 962, which is used to form a hard decision 976 and a soft decision using LLR metrics 978.
When a ML decoder is operating on n streams as shown in FIG. 10, the decoder 1020 complexity dramatically increases. In FIG. 10, the transformation shown in FIG. 5 is made by transformation 1000, whereby each y symbol 1002 is multiplied by the hermitian of Q to form symbol z 1022, and matrix R 1024 is used to generate a list of 64 possible estimated symbols 1028 in z symbol space. A distance metric is calculated to form a table, as before, but the size of the table 1026 is 64n entries, and the hard decision 1030 selects from among these 64n entries. The soft decision calculation 1032 calculates soft values for each of the 6n bits of hard decision data as described earlier. Because of the dramatic increase in decision decoder complexity associated with forming and evaluating n-tuples of hard and soft metrics for each of the possible QAM decision values for the n streams, a variety of architectures have been developed to reduce the complexity of finding hard and soft metrics for MIMO system decoders. One such system, described in U.S. Pat. No. 6,801,580, describes an Ordered Successive Interference Cancellation (OSIC) decoder, whereby the strongest symbol stream is selected and decoded first. The interference effect of this stream is cancelled from the second stream and the second stream is decoded and this process continues. A similar system is OSIC symbol-Chase, which uses the property shown in FIG. 5 whereby a transformation in variables results in received symbols y1 and y2 being converted to z1 and z2. Symbol stream x2 is derived from z2 alone and x1 is estimated from z1 and x2 combined.
A two channel OSIC symbol-chase demodulator is shown in FIG. 11. Transformation block 1100 orders the H matrix by moving the column with the largest norm to the right column to form H′, after which the QR matrix decomposition generates R and QH, which is used to convert receive vector Y 1104 into Z space by multiplication by QH, as was described earlier. The decoder 1128 receives R and Z1 from transformation block 1100, and R and Z1 are used to estimate x1 using z1 and all possible values of x2 from list 1116. These values are placed in a table 1118 accompanied by a distance metric, and the table entry with the minimum distance metric is selected, thereby generating estimates of x1 and x2 as the hard decision. The soft decision 1126 computes the LLR (Log Likelihood Ratio) metrics for each bit of x1 and x2 is calculated using |m02−m12|*sgn(hard decision). LLR metric computations are described in R. Pyndiah et al “Near Optimum Decoding of Product Codes”, IEEE Globecom 94, pg 339-43, November-December 1994.
Because of the transformation into Z space of 1100, the computation of soft decision metrics may be complicated by a problem where a particular hard decision bit does not have an entry with a complementary bit available for use by the LLR metrics. When this occurs, the use of either a default soft value or some other techniques like ZF soft-values may be used.